1. Field of the Invention
This invention relates generally to a system and method for authenticating a message transmitted in a wireless network and, more particularly, to a system and method for authenticating a message transmitted in a wireless network that employs both a digital signature and timed efficient stream loss-tolerant authentication (TESLA).
2. Discussion of the Related Art
Automotive active safety applications based on vehicle-to-vehicle (V2V) communications are a powerful service that can significantly reduce the number of automotive accidents, and related health care and insurance costs. Communications security is critical in these applications, since drivers of vehicles are expected to act in accordance with the warnings and advisories provided by the V2V applications. However, since communications security comes with both computational and bandwidth related overhead, it is important to reduce these overheads in order to obtain cost-effective implementations.
V2V safety applications, such as blind spot warning (BSW) and co-operative collision warning (CCW), rely on the repeated exchange of kinematical information between neighboring vehicles by V2V communications as per the wireless dedicated short range communication (DSRC) standard. These messages are typically transmitted periodically, at the frequency of 10 Hz per vehicle, and are authenticated using digital signatures based on an underlying public key infrastructure (PKI) in accordance with the IEEE 1609.2 standard specification. However, generating and verifying digital signatures consumes a significant amount of the share of the automotive processor. As the penetration of V2V-based active safety applications increases, there is a need for computationally efficient mechanisms for verification of messages since V2V-equipped vehicles would have to verify an increasing number of messages.
Each principal in a PKI system has a pair of keys, namely a private key and a public key. The private key is known only to the principal and the public key can be shared with other entities in the system. The keys can be visualized as a pair of functions Pr and Pu representing the private and public keys, respectively, and having the property M=Pr(Pu(M)) and M=Pu(Pr(M)), where M is the message that is to be secured using the keys. To ensure message integrity, the sender of the message signs the message with its private key, and adds this signature to the message. Upon receiving the message, the recipient can verify the signature of the message using the sender's public key.
Although the discussion herein pertains to V2V networking, the various broadcast authentication techniques have a much wider application. At an abstract level, the various broadcast authentication techniques discussed herein apply to communication networks where nodes broadcast information to one another in an authentic manner. In these networks, potentially every node is a sender and a receiver. Thus, a given node would broadcast its messages to multiple nodes, and it may also receive messages from multiple, and possibly different, nodes. It is desirable to conserve bandwidth in these types of communication networks. Bandwidth is consumed when the public key is sent ahead of the messages or packets. Additional bandwidth is also consumed when signatures are appended to messages or packets. It is also desirable to conserve the use of the vehicle computer or CPU for verifying received messages. If all nodes send messages at some rate, then a vehicle might receive many more messages as compared to how many it sends. Thus, generally, when computational overhead is referred to, the time taken for key generation and signature generation is ignored, and the process focuses only on the time taken for signature verification.
For the communications networks being discussed herein, the nodes would typically use an authentication protocol to achieve broadcast authenticity of the messages. An authentication protocol between a sender and a receiver enables the sender to send information to the receiver in an authentic manner. The authentication protocol used in the broadcast networks being discussed includes three steps, namely, key generation and public key distribution, signature generation and signature verification. For key generation and public key distribution, the sender executes a key generation algorithm for the authentication protocol and creates the public key, the private key and other variables. The sender then disseminates the public key to the receivers.
For signature generation, when the sender needs to send an authentic message, the sender creates the message and populates it with the appropriate information, and then uses a signature generation algorithm specific to the authentication protocol. In the case of digital signature algorithms, one public-private key pair can be used to sign a theoretically unlimited number of messages. The signature generation algorithm generally uses the hash-and-sign paradigm. This means that the message is first hashed into a constant length string of bits. The hashed version, also called the message digest, is then signed using the signature generation algorithm.
For signature verification, when a receiver needs to verify the authenticity of a received message, it needs to have in its possession the public key corresponding to the private key that signed the message. Assuming that the receiver does have the public key, it uses the signature verification algorithm for the authentication protocol. The verification algorithm also first hashes the message to derive the message digest, which is then subject to further verification steps.
At the security layer of the PKI protocol, the primary functionality of the broadcast authentication protocol is to filter bogus messages, i.e., those messages with the correct format, but with an invalid signature or authentication tag. The security strength of the broadcast authentication protocol is measured in n-bits of security, i.e., an attacker needs to perform O(2n) operations in order to forge a signature or authentication tag on a message. The IEEE 1609.2 standard recommends 128-bits of security.
While message authentication is sufficient to develop misbehavior detection algorithms at the application layer, non-repudiation is a required attribute to report misbehaving entities to the certifying authority (CA) in a PKI-based V2X (vehicle-to-infrastructure) security architecture. Note that the eventual eviction of misbehaving entities occurs via entries in a certificate revocation list (CRL) disseminated by the CA.
To verify whether a message is genuine or bogus consumes computational resources at a given node. In the wireless context, it is easy for a malicious entity without access to compromised keying material to create a bogus message, and inject those messages in the channel leading to a computational denial of service (DoS) attack. The notion of computational DoS resilience is introduced as the amount of computational work done by a receiver versus the amount of computational work done by the attacker. Unfortunately, digital signatures based on asymmetric key cryptography are particularly vulnerable to computational DoS attacks.
Note that broadcast authentication requires the asymmetric property that only the sender is able to generate the signature, or authentication tag, and any receiver is able to only verify the signature, or authentication tag. While asymmetric key cryptography can provide all the primitives required for broadcast authentication, primitives based on symmetric key cryptography are preferred because of their efficiency. Protocol constructions to attain broadcast authentication using symmetric key primitives include timed efficient stream loss-tolerant authentication (TESLA) and one-time signatures. In the vehicle ad-hoc network (VANET) context, however, these protocols piggyback on a PKI-based digital signature mechanism.
Persistent applications, such as BSW (Blind Spot Warning) or CCW (Cooperative Collision Warning), are based on vehicles transmitting on a continual basis, such as at the rate of ten messages per second. As vehicle densities increase, the rate of incoming messages to be verified increases linearly with the number of neighboring vehicles (assuming minimal losses in the wireless medium). However, the rate of outgoing messages to be signed is always bounded by the rate, such as ten messages per second. While it is possible to authenticate every outgoing message with a PKI-based digital signature, it may not be feasible to verify the digital signature of every received message at a node. Hence, the focus of efficient broadcast authentication is on efficient verification mechanisms. For example, consider 50 vehicles in the vicinity of a given tagged vehicle, each transmitting ten messages per second. The tagged vehicle receives up to 500 messages to be verified every second. Hence, for a stable system, the average verification time should be less than 2 ms.
There is an inherent asymmetry in the rate of incoming and outgoing messages in the context of a V2V network for active safety. Every V2V-equipped vehicle sends out a limited number of messages per unit time, but receives an increasing number of messages per unit time as the number of its neighbors increases. This asymmetry can be exploited by appending dual authenticators per message (one digital signature, and a lightweight authenticator). An authenticator is classified as lightweight based on the amount of time expended to generate or verify it. Nodes that come into the transmission range of the sender verify the digital signature at first, which enables them to verify the lightweight authenticator for subsequent messages.
As far as the problem of efficient broadcast authentication is concerned, there are various techniques available in the literature to address this problem. However, none of these available approaches is completely satisfactory. In particular, digital signatures result in high computational overhead, while one-time signatures, such as Merkle-Winternitz signatures, result in high communication overhead, and lightweight protocols, such as TESLA, result in delayed message authentication. Further, in one-time signatures, such as the Merkle-Winternitz signature, there is a trade-off between the computational overhead and the communication overhead, both of which increase in proportion with the number of bits being signed.
Suppose that for a given authentication mechanism, the average signing and verification times (in seconds) are denoted by Ts and Tv, respectively. Also, let Nout denote the rate at which the security layer receives outgoing messages to be signed per second, and let Nin denote the rate at which the security layer receives incoming messages to be verified per second. Since the utilization of the OBU (On-Board Unit) processor is at most 100%, it follows that for a stable system NoutTs+NinTv<1.
A brief description of the TESLA protocol is provided including its drawbacks in the vehicular context. This provides the motivation for modifications to the TESLA protocol for VANETs, which are then presented. The TESLA protocol is described in the context of a single sender and multiple receivers. The protocol is based on the delayed disclosure of symmetric keys. Initially, a sender appends to each message, a message authentication code (MAC) based on a symmetric key known only to itself. The receiver buffers the message without being able to authenticate them, which results in a message verification delay. A short time later, when the sender discloses the symmetric key, the receiver is able to authenticate buffered messages. The TESLA protocol is based on the property of loose time synchronization i.e., the receiver knows an upper bound on the sender's local time.
The sender divides time into L intervals of length TINT and computes a one-way hash-chain as described below. For a symmetric key K and a one-way hash function H(·), let H0(K)=K and let Hi+1(K)=H(Hi(K)) for integer values i≧0. The TESLA protocol also has a parameter called the key disclosure delay d expressed in units of the interval length TINT. At the start time T0, the sender computes the hash-chain, denoted by [K, H1(K), H2(K), . . . , HQ(K), . . . ] where Q>L. The sender decides on a time schedule to disclose symmetric keys of this hash-chain no earlier than the predetermined time instant.
The key disclosure schedule, denoted as ((T0, TINT, HQ(K)), signifies the sender's commitment to disclose the symmetric key HQ-w(K) no earlier than the time instant T0+w·TINT for all 1≦w≦L. Before time T0, the senders commitment to disclose symmetric keys is transmitted in an authentic manner to all receivers in a key disclosure schedule message. This key disclosure schedule message is signed with a digital signature, and requires support of the PKI security framework. All entities that have the key disclosure schedule ((T0, TINT, HQ(K)) follow the convention that interval w denotes the time interval [T0+w·TINT, T0+(w+1)·TINT. In accordance with the key disclosure schedule, the sender discloses the key HQ-w(K) during the interval w, for 0≦w≦L.
The transmission and reception processing is described at a node. When transmitting a packet, the sender adaptively selects a value of the key disclosure delay d. The sender discloses the symmetric key corresponding to the current time interval, and appends a MAC based on a symmetric key that will be disclosed d time intervals (of length TINT) later. Upon receiving a packet, the receiver:
1. Verifies the disclosed key is part of the hash-chain. The disclosed key is then used to verify buffered packers.
2. Determines the interval i in which the packet was transmitted based on the disclosed key in the packet, and an authentic version of the key disclosure schedule.
3. Based on its current time and a bound on the clock synchronization error, the receiver infers the latest possible interval x in which the sender could currently be in.
4. Determines the value of the parameters d in the message. If (x<i+d), the receiver buffers the packet for delayed verification. Otherwise, if (x≧i+d), it discards the packet as unsafe and drops it.
The primary advantage of TESLA is a significant improvement in the signing and verification time since the majority of messages are authenticated via a MAC based on a symmetric key. However, TESLA still requires support of the PKI-based security framework, since the key disclosure schedule has to be conveyed to all receivers in an authentic manner. In addition, TESLA requires clock synchronization at the nodes, and messages cannot be verified until the corresponding symmetric key is disclosed by the sender. Note that the parameters d and TINT of the TESLA protocol have to be carefully selected in order for the protocol to work well.
The main drawbacks of the TESLA protocols in the context of VANETs are described as follows. TESLA does not provide the non-repudiation property. While message authentication is sufficient to develop misbehavior detection algorithms at the application layer, non-repudiation is a required attribute for reporting misbehaving entities to the certifying authority (CA) in a PKI-based V2X security architecture. Note that the eventual eviction of misbehaving entities occurs via entries in a certificate revocation list (CRL) disseminated by the CA. DSRC (Dedicated Short Range Communications) channel switching between the control channel and service channel can also degrade the performance of TESLA.
V2X safety applications transmit real-time kinematic information (such as position, speed, and heading) in the message payload. Typically these messages are sent from the application layer to the security layer at the periodic rate of 100 ms. If TESLA key disclosure messages are always piggy-backed with application messages, then TINT=100 ms, where TINT denotes the length of the time intervals selected by the TESLA protocol. Hence, a lower bound on the message verification delay is 100 ms. This verification delay may be too large for V2X safety applications, such as collision avoidance applications. Note that a vehicle traveling at 90 kph (25 meters per second) would have moved 2.5 meters in 100 ms.
There are two types of potential attackers. An outside attacker that does not possess any compromised cryptographic credentials, such as private keys. The outside attacker can mount a DoS attack by sending bogus messages that have a valid format, but an incorrect authentication tag. This type of attacker steals a valid sender identification tag from the air, and transmits bogus messages on its behalf, overloading the receiving vehicles processor (buffers) for the computational DoS (memory DoS) attack. The other type of attacker is an inside attacker that has in its possession one or more compromised cryptographic credentials, such as the private keys. This type of attacker can transmit a spurious message, i.e., message with incorrect or invalid payload by cryptographically correct authentication tag(s). In the case of a transmitted message being authenticated by both a digital signature and a TESLA MAC, referred to as a TESLA authentication and digital signature (TADS) protocol, this type of attacker can mount a particularly insidious attack, referred to as a “correct MAC fake digital signature” attack. This type of attacker can mount a correct MAC fake digital signature DoS attack by transmitting messages with correct message authentication codes, but fake digital signatures. These messages can convey false information where the attacker does not get implicated if only the MAC is verified.